package com.lwl.shua.class01;

/**
 * @author lwl
 * @Description 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 * <p>
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * @date 2025/9/6 10:42
 */
public class Code05Lc329LongestIncreasingPath {

    public static int longestIncreasingPath(int[][] matrix) {
        int ans = 0;
        int[][] memoryCache = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                ans = Math.max(ans, process(i, j, matrix, memoryCache));
            }
        }
        return ans;
    }

    private static int process(int i, int j, int[][] matrix, int[][] memoryCache) {
        if (memoryCache[i][j] != 0) {
            return memoryCache[i][j];
        }

        // 向上走
        int up = i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j] ? process(i - 1, j, matrix, memoryCache) : 0;
        int down = i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j] ? process(i + 1, j, matrix, memoryCache) : 0;
        int left = j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j] ? process(i, j - 1, matrix, memoryCache) : 0;
        int right = j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j] ? process(i, j + 1, matrix, memoryCache) : 0;
        int ans = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
        memoryCache[i][j] = ans;
        return ans;
    }
}
